The H.264/AVC standard and many other moving picture encoding systems employ a motion compensation method in which an image (one frame) is divided into a plurality of blocks and the motion of each block in relation to a previously encoded image is estimated. As the block size is reduced, more precise motion estimation becomes possible, but the encoding rate increases because motion vector information must be encoded for each block.
For this reason, the H.264/AVC standard employs a strategy (variable block size motion compensation) in which the block (referred to below as partition) size that is used is switched by selecting the optimal block size from among several motion compensation block sizes, (see non-patent document 1).    Non-patent document 1: “Kaitei-ban H.264/AVC Kyokasho (H.264/AVC TEXTBOOK revised version)”, supervised by Sakae Ohkubo, published by Inpress NetBusiness Company Co., January, 2006, pp. 113 to 119